﻿/*THÔNG TIN*********************************************************************
 *Tập tin		: Graph_Spanning_Tree.h
 *Mô tả			: Thư viện các thuật toán tìm cây khung
 *Ngày tạo		: 29/08/2012
 *Cập nhật cuối	: 07/11/2012
 *Trình dịch	: Microsoft Visual C++ 11.0
 *Tác giả		: Vũ Văn Hiệp
 *Thư điện tử	: muteszhacker@gmail.com
*******************************************************************************/

/*Lớp các thuật toán tìm cây khung nhỏ nhất*/
class SPANTREE	: public GRAPH	{
private:
	// Cấu trúc mô tả cạnh
	struct EDGE_2	{
		uint16_t begin, end;
		double length;
	};

	// Tổng trọng số cây khung nhỏ nhất
	double sum_length;

	// Mảng lưu các cạnh của cây khung nhỏ nhất
	vector <EDGE_2> SpanTree_edge;

public:
	// Phương thức khởi tạo
	SPANTREE();

	// Khởi tạo cho thuật toán Prim
	void Initiate_Prim();
	// Thuật toán Prim tìm cây khung nhỏ nhất
	void Prim();

	// In kết quả cây khung tìm được ra file .out
	void Print_result_to_out(string input_file);
	// In cây khung vào file .dot
	void Print_result_to_dot(string input_file);
};/*Kết thúc khai báo lớp SPANTREE*/

/*Phương thức khởi tạo*/
SPANTREE :: SPANTREE()	{
	sum_length = 0;
	SpanTree_edge.clear();
}/*Kết thúc phương thức SPANTREE*/

/*Khởi tạo cho thuật toán Prim*/
void SPANTREE :: Initiate_Prim()	{
	Random_source_and_target();
	
	cout << "Thuc hien thuat toan tim cay khung nho nhat..........";
	start_time = clock();
}/*Kết thúc phương thức Initiate_Prim*/

/*Giải thuật Prim tìm cây khung nhỏ nhất*/
void SPANTREE :: Prim()	{
	vector <bool> mark ( Get_vertices() );
	mark[0] = true;

	do	{
		double min = UINT16_MAX;
		uint16_t last_i = UINT16_MAX, last_j = UINT16_MAX;

		for (uint16_t i=0; i!=Get_vertices(); ++i)
			for (uint16_t j=0; j!=Get_vertices(); ++j)
				if (Get_length(i, j)<min && mark[i] && !mark[j])	{
					min = Get_length(i, j);
					last_i = i;
					last_j = j;
				}

				if (last_j == UINT16_MAX)
					return;

				mark[last_j] = true;

				EDGE_2 e;
				e.begin = last_i;
				e.end = last_j;
				e.length = Get_length(last_i, last_j);
				SpanTree_edge.push_back(e);

				sum_length += Get_length(last_i, last_j);
	} while (SpanTree_edge.size() != Get_vertices() - 1);
}/*Kết thúc phương thức Prim*/

/*In kết quả cây khung ra file .out*/
void SPANTREE :: Print_result_to_out(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Prim", ".out");

	// Bắt đầu lưu kết quả
	f << "Cac canh cua cay khung la:\n";
	
	for (uint16_t i=0; i!=SpanTree_edge.size(); ++i)
		f << SpanTree_edge[i].begin+1 << ", " << SpanTree_edge[i].end+1 << ", " << SpanTree_edge[i].length << "\n";

	f << "Tong trong so cay khung la " << sum_length << "\n";

	f.close();
	cout << "Xong.\n";
}/*Kết thúc phương thức Print_result_to_out*/

/*In cây khung vào file .dot*/
void SPANTREE :: Print_result_to_dot(string input_file)	{
	string input_header(input_file.begin(), input_file.end()-4);
	fstream f = New_output_file(input_header, "_Prim", ".dot");

	f << "graph " << input_header << "_Prim {\n";

	for (uint16_t i=0; i<Get_vertices(); ++i)
		for (uint16_t j=0; j<Get_vertices(); ++j)	{
			if (Get_length(i, j) != UINT16_MAX)	{
				f << i+1 << " -- " << j+1 << " [";

				uint16_t k;

				for (k=0; k!=SpanTree_edge.size(); ++k)
					if (SpanTree_edge[k].begin == i && SpanTree_edge[k].end == j)
						break;

				if (k == SpanTree_edge.size())
					f << "style = dotted, ";

				f << "label = \"" << Get_length(i, j) << "\"]\n";
			}
		}

		f << "label = \"\\n\\nCay khung nho nhat co do dai " << sum_length << " cua do thi\\n"
		  << "dung thuat toan Prim voi du lieu tu file " << input_file << "\"\n}";

	f.close();
	cout << "Xong.\n";
}/*Kết thúc hàm Print_result_to_dot*/
